題目：
請寫一個方法，輸入一個int陣列，陣列內的數字代表路面高度，請輸出路上最多可以積多少水

反正就是路上的坑洞可以積多少水XD

點我前往LeetCode題目

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

今天這題是昨天題目的進階題目，我們會用到昨天的左右旗子概念，建議大家先看看昨天的題目

今天這題的集水區應該要變成下圖這樣（用文字說明太抽象所以改用圖片）

左邊是上一題的，右邊是今天題目的。

上一題的概念是每道牆壁中間都有1的空間，也就是假設牆壁不占空間，而且最後只有兩道牆壁會出現。而今天這題的牆壁(地板)則是佔了整格空間，外加每道牆壁都會出現，不是昨天那種N取2出現

那昨天的插旗子要怎麼套用到今天題目呢？大家要知道用旗子算集水區的核心概念就是：
比較矮的牆往另一邊掃過去，一定會對應到更高的牆，所以要移動的旗子是比較矮的牆那根

因為如果是比較高的牆，移過去沒對到更高的牆就爆炸啦！

再來移動的同時我們也要記錄牆的高度，來讓我們去算會積多少水。而如果遇到更高的牆，就把牆壁的高度設成更高的高度，如果沒有，就把高度減掉地板高度，就能拿到水量

具體運作像下面這張圖（上面都很抽象，所以我們還是看GIF吧，注意牆高的變化）

所以我們可以得到下面這段程式碼

class Solution {
    public int trap(int[] height) {
        if(height.length==0) return 0;
        int left=0, right=height.length-1, size=0, leftMax=height[0], rightMax=height[height.length-1];
        while(left<right) {
            if(leftMax>rightMax){
                rightMax=Math.max(rightMax,height[right-1]);
                size+=rightMax-height[--right];
            } else {
                leftMax=Math.max(leftMax,height[left+1]);
                size+=leftMax-height[++left];
            }
        }
        return size;
    }
}

if(height.length==0) return 0;

這段就是避免有人傳空的東西進來

int left=0, right=height.length-1, size=0, leftMax=height[0], rightMax=height[height.length-1];

left和right就是旗子的位置，而leftMax和rightMax，就是左右旗子掃過的最高牆壁高度

while(left<right) {
    if(leftMax>rightMax){
        rightMax=Math.max(rightMax,height[right-1]);
        size+=rightMax-height[--right];
    } else {
        leftMax=Math.max(leftMax,height[left+1]);
        size+=leftMax-height[++left];
    }
}

接著，我們移動牆壁高度比較低的那根旗子，如果新掃到的牆壁高度比較高，就更新牆壁高度，如果沒有，就算水量。

如此一來就能算出坑洞的集水量